package leetcode;


import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class LeetCode914 {
    public boolean hasGroupsSizeX1(int[] deck) {
        if (deck.length == 1)
            return false;
        Map<Integer, Integer> dict = new HashMap<>();
        for (int i = 0; i < deck.length; i++) {
            dict.put(deck[i], dict.getOrDefault(deck[i], 0) + 1);
        }
        int min = dict.get(deck[0]);
        for (Map.Entry<Integer, Integer> e : dict.entrySet()) {
            min = Math.min(min, e.getValue());
        }
        if (min == 1)
            return false;
        while (min % 2 == 0) {
            if (min == 2)
                break;
            min /= 2;
        }
        for (Map.Entry<Integer, Integer> e : dict.entrySet()) {
            if (e.getValue() % min != 0)
                return false;
        }
        return true;
    }

    //------------------------------------------------------------------
    public boolean hasGroupsSizeX(int[] deck) {
        int[] count = new int[10000];
        for (int c : deck)
            count[c]++;

        int g = -1;
        for (int i = 0; i < 10000; ++i)
            if (count[i] > 0) {
                if (g == -1)
                    g = count[i];
                else
                    g = gcd(g, count[i]);
            }

        return g >= 2;
    }

    //最大公约数
    public int gcd(int x, int y) {
        return x == 0 ? y : gcd(y % x, x);
    }
}
